//
// Description: 5270. 网格中的最小路径代价
// Created by Loading on 2022/6/13.
//

#include <bits/stdc++.h>

using namespace std;

int minPathCost(vector<vector<int>> &grid, vector<vector<int>> &moveCost) {
    int m = grid.size();
    int n = grid[0].size();

    // 线性dp，dp[i][j] 表示到 (i,j) 位置时的最小路径代价
    int dp[m][n];
    // 初始化
    memset(dp, 0x3f, sizeof dp);
    for (int i = 0; i < n; ++i) {
        dp[0][i] = grid[0][i];
    }

    for (int i = 1; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            // 枚举从哪一列转移而来
            for (int k = 0; k < n; ++k) {
                int t = grid[i - 1][k];
                dp[i][j] = min(dp[i][j], dp[i - 1][k] + moveCost[t][j] + grid[i][j]);
            }
        }
    }

    return *min_element(dp[m - 1], dp[m - 1] + n);
}

int main() {
    vector<vector<int>> grid = {{5, 3},
                                {4, 0},
                                {2, 1}};
    vector<vector<int>> moveCost = {{9,  8},
                                    {1,  5},
                                    {10, 12},
                                    {18, 6},
                                    {2,  4},
                                    {14, 3}};

    auto res = minPathCost(grid, moveCost);

    cout << res << endl;

    return 0;
}